package com.sinaapp.gavinzhang.GSpider.plugin.bloomfilter;

import com.sinaapp.gavinzhang.GSpider.core.AbstractGWebUrlList;

/**
 * 实验性质，布隆处理器。成功率低
 * Created by gavin on 15-8-4.
 */
public class BloomVisitedUrlList extends AbstractGWebUrlList {
    private static final int MIN_CAPACITY = 8388608;
    private int capacity;
    private int[] bloom;
    private int length=0;

    public BloomVisitedUrlList() {
        this(MIN_CAPACITY);
    }

    public BloomVisitedUrlList(int capacity) {
        this.capacity =  (capacity <MIN_CAPACITY)?MIN_CAPACITY:roundUpToPowerOf2(capacity);
        this.bloom = new int[this.capacity];
    }

    @Override
    public boolean exist(String webUrl) {
        long position = BKDRHash(webUrl);
        //position = Math.abs(position);
        return (bloom[(int)(position&(capacity-1))]&(1<<(position%32)))!=0;

    }

    @Deprecated
    @Override
    public String get() {
        return null;
    }

    @Override
    public AbstractGWebUrlList add(String webUrl) {
        long position = BKDRHash(webUrl);
        if (!exist(webUrl))
        {
            length++;
        }
        bloom[(int)(position&(capacity-1))] |= 1<<(position%32);
        //length++;
        return this;
    }

    @Deprecated
    @Override
    public AbstractGWebUrlList remove(String webUrl) {
        return null;
    }

    @Override
    public int size() {
        return length;
    }

    public static int DJBHash(String str)
    {
        int hash = 5381;
        for(int i = 0; i < str.length(); i++)
        {
            hash = ((hash << 5) + hash) + str.charAt(i);
        }
        return hash;
    }

    /** 分布性比较好*/
    public long BKDRHash(String str)
    {
        int seed = 131; // 31 131 1313 13131 131313 etc..
        long hash = 0;
        for(int i = 0; i < str.length(); i++)
        {
            hash = (hash * seed) + str.charAt(i);
        }
        return hash&((capacity<<5)-1);
    }

    public long PJWHash(String str)
    {
        long BitsInUnsignedInt = (long)(4 * 8);
        long ThreeQuarters     = (long)((BitsInUnsignedInt  * 3) / 4);
        long OneEighth         = (long)(BitsInUnsignedInt / 8);
        long HighBits          = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
        long hash              = 0;
        long test              = 0;
        for(int i = 0; i < str.length(); i++)
        {
            hash = (hash << OneEighth) + str.charAt(i);
            if((test = hash & HighBits)  != 0)
            {
                hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
            }
        }
        return hash&((((long)capacity)<<5)-1);
    }

    /**java自带的String处理*/
    public int hash(String str)
    {
        //return sun.misc.Hashing.stringHash32(str);
        int h = 1313131;
        h ^= str.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= Integer.MAX_VALUE
                ? Integer.MAX_VALUE
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }
}
